#include <stdio.h>

//typedef struct Tree
//{
//    char val;
//    struct Tree* left;
//    struct Tree* right;
//}T;
//
//T* BuyNode(char x)
//{
//    T* newnode = (T*)malloc(sizeof(T));
//    newnode->val = x;
//    newnode->left = newnode->right = NULL;
//    return newnode;
//}
//T* CreatTree(char arr[], int* pi)
//{
//    if (arr[*pi] == '#')
//    {
//        (*pi)++;
//        return NULL;
//    }
//    T* root = BuyNode(arr[*pi]);
//    (*pi)++;
//    root->left = CreatTree(arr, pi);
//    root->right = CreatTree(arr, pi);
//    return root;
//}
//void InOrder(T* root)
//{
//    if (root == NULL)
//        return;
//    InOrder(root->left);
//    printf("%c ", root->val);
//    InOrder(root->right);
//}
//int main() {
//    char arr[100];
//    scanf("%s", arr);
//    int i = 0;
//
//    T* root = CreatTree(arr, &i);
//    InOrder(root);
//    return 0;
//}

//bool isSametree(struct TreeNode* root, struct TreeNode* subRoot) {
//    if (root == NULL && subRoot == NULL)
//        return  true;
//    if (root == NULL || subRoot == NULL)
//        return false;
//    if (root->val != subRoot->val)
//        return false;
//    return isSametree(root->left, subRoot->left) && isSametree(root->right, subRoot->right);
//}
//bool isSubtree(struct TreeNode* root, struct TreeNode* subRoot) {
//    if (root == NULL)
//        return false;
//    if (isSametree(root, subRoot))
//        return true;
//    return isSubtree(root->left, subRoot) || isSubtree(root->right, subRoot);
//}

//bool isSametree(struct TreeNode* root, struct TreeNode* subRoot) {
//    if (root == NULL && subRoot == NULL)
//        return  true;
//    if (root == NULL || subRoot == NULL)
//        return false;
//    if (root->val != subRoot->val)
//        return false;
//    return isSametree(root->left, subRoot->right) && isSametree(root->right, subRoot->left);
//}
//bool isSymmetric(struct TreeNode* root) {
//    return isSametree(root->left, root->right);
//}

//bool isUnivalTree(struct TreeNode* root) {
//    if (root == NULL)
//        return true;
//    if (root->left && root->val != root->left->val)
//    {
//        return false;
//    }
//    if (root->right && root->val != root->right->val)
//    {
//        return false;
//    }
//    return isUnivalTree(root->left) && isUnivalTree(root->right);
//}

//int Treesize(struct TreeNode* root)
//{
//    if (root == NULL)
//        return 0;
//    return 1 + Treesize(root->left) + Treesize(root->right);
//}
//void oreder(struct TreeNode* root, int* arr, int* pi)
//{
//    if (root == NULL)
//        return;
//    oreder(root->left, arr, pi);
//    arr[(*pi)++] = root->val;
//    oreder(root->right, arr, pi);
//
//}
//int* inorderTraversal(struct TreeNode* root, int* returnSize) {
//    *returnSize = Treesize(root);
//    int* arr = (int*)malloc(*returnSize * sizeof(int));
//    int i = 0;
//    oreder(root, arr, &i);
//    return arr;
//}